#include <stdio.h>
#include <stdlib.h>

typedef struct stacktag {
	int data;

	struct stacktag *older;
}stack;

stack * push (stack *s, int data)
{
	stack *node;

	node = malloc(sizeof(stack));

	node->data = data;
	node->older = s;

	//printf ("Pushed %d\n", data);

	return node;
}

stack * pop (stack *s, int *value)
{
	stack *temp = NULL;

	if (s) {
		*value = s->data;
		//printf ("Popped the value %d\n", *value);
		temp = s->older;
		free (s);
	}
		
	return temp;
}


typedef struct queuetag {
	stack *s1;
	stack *s2;
}queue;

queue * enq (queue * q, int data)
{
	if (q)
		q->s1 = push (q->s1, data);
	else {
		q = malloc (sizeof(queue));
		q->s1 = push (NULL, data);
		q->s2 = NULL;
	}

	printf ("Enqueued %d\n", data);

	return q;
}

queue * deq (queue *q, int *data)
{
	if (!q)
		printf ("No more elements in the Queue. Emptied\n");
	else {
		if (!q->s2) {

			if (!q->s1) {
				printf ("No elements in the queue\n");
				free (q);
				return NULL;
			}
			
			int s1_has_elements = 1;
			while (s1_has_elements) {
				int tmp;
				q->s1 = pop (q->s1, &tmp);
				q->s2 = push (q->s2, tmp);
				if (!q->s1) {
					s1_has_elements = 0;
					break;
				}
			}
		}
		
#if 0
		if (!q->s2) {
			q = NULL;
			printf ("Emptied the queue\n");
			return NULL;
		}
#endif

		q->s2 = pop (q->s2, data);
		printf ("Dequeued %d\n", *data);
	}

	return q;
}

int main()
{
	int val;
	queue *q;

	q = enq (NULL, 1);
	q = enq (q, 2);
	q = enq (q, 3);
	q = enq (q, 4);
	q = enq (q, 5);
	q = enq (q, 6);
	q = deq (q, &val);
	q = deq (q, &val);
	q = deq (q, &val);
	q = deq (q, &val);
	q = deq (q, &val);
	q = deq (q, &val);
	q = deq (q, &val);
	q = deq (q, &val);
	q = deq (q, &val);
	q = deq (q, &val);
	q = enq (q, 2);
	q = enq (q, 3);
	q = deq (q, &val);
	q = deq (q, &val);
	q = deq (q, &val);
	q = deq (q, &val);
	q = deq (q, &val);

	return 0;
}
